package hwThree4;

public class LinearProbingHashST<Key, Value> {
    private int n; // 键值对数目
    private int m; // 散列表大小
    private Key[] keys; // 键数组
    private Value[] values; // 值数组

    public LinearProbingHashST(int capacity) {
        m = capacity;
        n = 0;
        keys = (Key[]) new Object[m];
        values = (Value[]) new Object[m];
    }

    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % m;
    }

    public void put(Key key, Value value) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        if (value == null) {
            delete(key);
            return;
        }
        if (n >= m / 2) resize(2 * m); // 动态扩展散列表

        int i;
        for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
            if (keys[i].equals(key)) {
                values[i] = value;
                return;
            }
        }
        keys[i] = key;
        values[i] = value;
        n++;
    }

    public Value get(Key key) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
            if (keys[i].equals(key)) return values[i];
        }
        return null;
    }

    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("Key cannot be null");
        if (!contains(key)) return;

        int i = hash(key);
        while (!key.equals(keys[i])) {
            i = (i + 1) % m;
        }

        keys[i] = null;
        values[i] = null;

        i = (i + 1) % m;
        while (keys[i] != null) {
            Key keyToRehash = keys[i];
            Value valueToRehash = values[i];
            keys[i] = null;
            values[i] = null;
            n--;
            put(keyToRehash, valueToRehash);
            i = (i + 1) % m;
        }

        n--;
        if (n > 0 && n <= m / 8) resize(m / 2);
    }

    public boolean contains(Key key) {
        return get(key) != null;
    }

    private void resize(int capacity) {
        LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<>(capacity);
        for (int i = 0; i < m; i++) {
            if (keys[i] != null) temp.put(keys[i], values[i]);
        }
        keys = temp.keys;
        values = temp.values;
        m = temp.m;
    }

    // 方法：计算一次命中查找的平均成本
    public double averageSearchCostHit() {
        int totalCost = 0; // 总查找成本
        int count = 0;     // 键的数量

        for (int i = 0; i < m; i++) {
            if (keys[i] != null) { // 遍历所有键
                int cost = 0;
                int j = hash(keys[i]); // 从键的哈希值开始探测
                while (!keys[j].equals(keys[i])) { // 模拟查找过程
                    cost++;
                    j = (j + 1) % m;
                }
                totalCost += (cost + 1); // 加 1 表示找到目标键的位置
                count++;
            }
        }

        return count == 0 ? 0.0 : (double) totalCost / count; // 平均成本
    }

    public static void main(String[] args) {
        LinearProbingHashST<String, Integer> st = new LinearProbingHashST<>(10);
        st.put("S", 1);
        st.put("E", 2);
        st.put("A", 3);
        st.put("R", 4);
        st.put("C", 5);
        st.put("H", 6);
        st.put("X", 7);
        st.put("M", 8);
        st.put("P", 9);
        st.put("L", 10);

        System.out.println("Average search cost for hit: " + st.averageSearchCostHit());
    }
}
